r"""
Known lower bounds on the number of Mutually Orthogonal Latin
Squares (MOLS) of a given size.

This module consists (almost) entirely of an internal, constant tuple
of python integers corresponding to Table 3.87 in the Handbook of
Combinatorial Designs, 2nd edition, by Colbourn and Dinitz. One public
function, :func:`lower_bound`, is provided to access it.

Make sure we have all of the entries::

    sage: from sage.combinat.designs import MOLS_handbook_data
    sage: len(MOLS_handbook_data._LOWER_BOUNDS)
    10000

Jeff Dinitz's website (at UVM) provides the following two updates to
the table as printed in the second edition::

    sage: from sage.combinat.designs import MOLS_handbook_data
    sage: MOLS_handbook_data.lower_bound(60)
    5
    sage: MOLS_handbook_data.lower_bound(7968)
    31

"""

_LOWER_BOUNDS: tuple[int, ...]
_LOWER_BOUNDS = (
 0,0,1,2,3,4,1,6,7,8,2,10,5,12,3,4,15,16,3,18,                            # 0
 4,5,3,22,7,24,4,26,5,28,4,30,31,5,4,5,8,36,4,5,                          # 20
 7,40,5,42,5,6,4,46,8,48,6,5,5,52,5,6,7,7,5,58,                           # 40
 5,60,5,6,63,7,5,66,5,6,6,70,7,72,5,7,6,6,6,78,                           # 60
 9,80,8,82,6,6,6,6,7,88,6,7,6,6,6,6,7,96,6,8,                             # 80
 8,100,6,102,7,7,6,106,6,108,6,6,13,112,6,7,6,8,6,6,                      # 100
 7,120,6,6,6,124,6,126,127,7,6,130,6,7,6,7,7,136,6,138,                   # 120
 6,7,6,10,10,7,6,7,6,148,6,150,7,8,8,7,6,156,7,6,                         # 140
 9,7,6,162,6,7,6,166,7,168,6,8,6,172,6,6,14,9,6,178,                      # 160
 6,180,6,6,7,9,6,10,6,8,6,190,7,192,6,7,6,196,6,198,                      # 180
 7,8,6,7,6,8,6,8,14,11,10,210,6,7,6,7,7,8,6,10,                           # 200
 6,12,6,222,13,8,6,226,6,228,6,7,7,232,6,7,6,7,6,238,                     # 220
 7,240,6,242,6,7,6,12,7,7,6,250,6,12,9,7,255,256,6,12,                    # 240
 6,8,8,262,7,8,7,10,7,268,7,270,15,16,6,13,10,276,6,9,                    # 260
 7,280,6,282,6,12,6,7,15,288,6,6,6,292,6,6,7,10,10,12,                    # 280
 7,7,7,7,15,15,6,306,7,7,7,310,7,312,7,10,7,316,7,10,                     # 300
 15,15,6,16,8,12,6,7,7,9,6,330,7,8,7,6,8,336,6,7,                         # 320
 6,10,10,342,7,7,6,346,6,348,8,12,18,352,6,9,7,9,6,358,                   # 340
 8,360,6,7,7,10,6,366,15,15,7,15,7,372,7,15,7,13,7,378,                   # 360
 7,12,7,382,15,15,7,15,7,388,7,16,7,8,7,7,8,396,7,7,                      # 380
 15,400,7,15,11,8,7,15,8,408,7,13,8,12,10,9,18,15,7,418,                  # 400
 7,420,7,15,7,16,6,7,7,10,6,430,15,432,6,15,6,18,7,438,                   # 420
 7,15,7,442,7,13,7,11,15,448,7,15,7,7,7,15,7,456,7,16,                    # 440
 7,460,7,462,15,15,7,466,8,8,7,15,7,15,10,18,7,15,6,478,                  # 460
 15,15,6,15,8,7,6,486,7,15,6,490,6,16,6,7,15,15,6,498,                    # 480
 7,12,9,502,7,15,6,15,7,508,6,15,511,18,7,15,8,12,8,15,                   # 500
 8,520,10,522,12,15,8,16,15,528,7,15,8,12,7,15,8,15,10,15,                # 520
 12,540,7,15,18,7,7,546,7,8,7,18,7,7,7,7,7,556,7,12,                      # 540
 15,7,7,562,7,7,6,7,7,568,6,570,7,7,15,22,8,576,7,7,                      # 560
 7,8,7,10,7,8,7,586,7,18,17,7,15,592,8,15,7,7,8,598,                      # 580
 14,600,12,15,7,15,16,606,18,15,7,15,8,612,8,15,7,616,7,618,              # 600
 8,22,8,15,15,624,7,8,8,16,7,630,7,8,7,8,7,12,7,8,                        # 620
 9,640,7,642,7,7,7,646,8,10,7,7,7,652,7,7,15,15,7,658,                    # 640
 7,660,7,15,7,15,7,22,7,15,7,15,15,672,7,24,8,676,7,15,                   # 660
 7,15,7,682,8,15,7,15,15,15,7,690,8,15,7,15,7,16,7,15,                    # 680
 8,700,7,18,15,15,7,15,8,708,7,15,7,22,21,15,7,15,8,718,                  # 700
 15,9,8,12,10,24,12,726,7,728,16,16,18,732,7,7,22,10,8,738,               # 720
 7,7,7,742,7,15,7,8,7,10,7,750,15,15,8,15,8,756,8,15,                     # 740
 7,760,8,15,8,15,8,15,15,768,8,15,8,772,8,24,23,15,8,18,                  # 760
 8,18,7,26,15,15,10,786,12,15,7,15,20,15,18,15,8,796,22,16,               # 780
 24,15,8,15,8,15,8,15,8,808,8,810,8,15,8,15,15,18,8,8,                    # 800
 8,820,8,822,8,15,8,826,8,828,8,15,12,16,7,8,7,26,25,838,                 # 820
 8,840,8,20,8,10,8,16,15,15,12,22,7,852,16,15,22,856,7,858,               # 840
 22,15,24,862,26,15,7,15,8,15,9,15,7,15,7,15,7,876,8,15,                  # 860
 15,880,8,882,8,15,7,886,7,15,8,15,10,18,8,15,13,15,8,28,                 # 880
 27,16,8,8,8,22,8,906,8,18,10,910,15,14,8,15,16,10,18,918,                # 900
 24,8,22,12,24,24,26,8,28,928,7,18,7,7,7,14,7,936,7,15,                   # 920
 7,940,7,22,15,15,7,946,7,12,12,15,7,952,7,15,7,15,8,15,                  # 940
 15,960,29,15,8,15,8,966,8,15,8,970,10,18,12,15,15,976,16,18,             # 960
 18,15,7,982,27,15,24,15,26,22,28,990,31,31,7,15,8,996,25,26,             # 980
 7,15,21,16,19,15,7,18,15,1008,13,18,8,1012,9,22,7,28,7,1018,             # 1000
 7,1020,7,30,1023,24,7,15,9,15,9,1030,7,1032,7,15,8,16,9,1038,            # 1020
 15,15,8,15,8,15,8,15,8,1048,8,1050,8,15,8,15,15,16,8,8,                  # 1040
 8,1060,8,1062,8,15,8,15,10,1068,7,15,15,28,7,24,7,15,8,15,               # 1060
 12,22,8,15,8,15,8,1086,16,15,8,1090,8,1092,8,15,8,1096,8,15,             # 1080
 8,15,8,1102,15,15,8,26,8,1108,8,18,8,15,8,15,8,1116,7,15,                # 1100
 16,18,7,1122,7,15,7,22,8,1128,7,15,8,15,10,9,15,15,7,16,                 # 1120
 7,8,7,15,7,15,7,30,30,15,7,1150,15,1152,7,15,8,26,12,24,                 # 1140
 12,26,7,1162,16,18,18,15,15,15,22,1170,24,15,26,24,28,15,30,30,          # 1160
 8,1180,8,15,31,15,8,1186,8,28,8,15,8,1192,8,15,8,15,8,15,                # 1180
 15,1200,8,15,8,15,8,16,8,15,8,15,8,1212,8,15,18,1216,7,22,               # 1200
 7,15,8,1222,7,24,7,15,7,1228,7,1230,15,9,8,15,7,1236,7,15,               # 1220
 7,16,8,10,8,7,8,28,8,1248,8,8,7,7,7,8,8,8,7,1258,                        # 1240
 7,12,23,7,15,15,9,15,9,26,9,30,30,23,8,15,9,1276,9,1278,                 # 1260
 15,30,10,1282,12,15,9,24,16,1288,18,1290,8,18,22,15,24,1296,26,15,       # 1280
 28,1300,30,1302,8,15,8,1306,30,15,8,15,31,15,12,15,8,15,8,1318,          # 1300
 8,1320,8,26,8,24,7,1326,15,15,8,1330,8,30,30,15,8,15,9,30,               # 1320
 12,15,8,30,15,30,12,15,9,26,16,24,18,15,9,20,22,22,24,15,                # 1340
 26,1360,28,28,30,30,9,1366,28,1368,30,15,9,1372,30,15,31,16,8,15,        # 1360
 8,1380,8,15,8,15,8,18,8,15,8,15,15,15,8,15,8,10,9,1398,                  # 1380
 10,15,8,22,8,8,8,15,10,1408,8,16,7,9,9,22,9,12,7,8,                      # 1400
 9,28,7,1422,15,24,9,1426,9,1428,7,26,7,1432,9,15,7,15,7,1438,            # 1420
 15,15,7,15,9,15,9,1446,7,15,7,1450,7,1452,9,15,15,30,30,1458,            # 1440
 8,15,8,30,8,15,8,30,10,30,12,1470,22,30,16,28,18,15,8,24,                # 1460
 22,1480,24,1482,26,18,28,1486,30,1488,13,15,8,1492,30,15,8,15,30,1498,   # 1480
 30,18,9,15,31,15,9,15,9,14,9,1510,9,24,9,9,9,36,9,30,                    # 1500
 30,9,9,1522,9,30,9,9,9,30,10,1530,12,9,9,30,16,30,18,18,                 # 1520
 8,26,22,1542,24,8,26,20,28,1548,30,30,15,1552,8,15,30,8,8,1558,          # 1540
 30,15,30,15,8,15,30,1566,31,15,8,1570,8,15,12,15,8,18,8,1578,            # 1560
 8,15,8,1582,15,24,8,8,8,15,8,36,7,26,8,15,8,1596,8,15,                   # 1580
 24,1600,8,15,8,15,8,1606,8,1608,8,15,8,1612,7,15,15,15,8,1618,           # 1600
 8,1620,7,15,7,15,7,1626,7,15,7,15,24,22,8,15,8,1636,7,15,                # 1620
 7,15,7,30,30,15,7,26,15,30,7,15,11,30,10,30,12,1656,7,30,                # 1640
 16,30,18,1662,15,30,22,1666,24,1668,26,24,28,22,30,30,19,15,7,22,        # 1660
 30,1680,9,15,30,15,30,15,9,15,30,18,30,1692,9,15,31,1696,9,1698,         # 1680
 9,15,8,15,8,15,8,15,8,1708,21,28,15,15,8,15,10,16,7,15,                  # 1700
 8,1720,9,1722,9,15,7,15,26,21,8,15,8,1732,7,15,7,15,7,36,                # 1720
 9,1740,8,15,15,15,8,1746,8,15,8,16,9,1752,9,15,9,15,8,1758,              # 1740
 26,15,8,40,9,15,8,15,8,28,8,27,8,15,8,24,15,1776,9,15,                   # 1760
 8,15,8,1782,8,15,8,1786,8,1788,8,15,15,15,9,15,8,15,8,15,                # 1780
 8,1800,8,15,9,15,8,30,15,26,8,1810,8,36,7,15,9,22,9,16,                  # 1800
 9,15,9,1822,26,24,9,15,9,30,30,1830,9,15,9,30,9,15,9,30,                 # 1820
 15,30,12,18,9,30,16,1846,18,1848,9,30,22,16,24,15,28,30,28,28,           # 1840
 30,1860,25,22,8,22,30,1866,8,18,30,1870,30,1872,8,15,30,1876,30,1878,    # 1860
 8,15,30,8,8,8,8,15,31,1888,8,30,30,15,8,15,8,30,8,15,                    # 1880
 8,1900,10,30,15,15,8,1906,16,30,18,15,8,1912,22,15,24,26,26,30,          # 1900
 28,30,30,30,27,9,7,40,30,9,8,1930,30,1932,30,8,15,15,30,15,              # 1920
 30,10,8,28,30,15,8,15,8,1948,30,1950,31,15,8,15,8,18,8,15,               # 1940
 8,36,8,15,8,15,8,15,15,15,8,26,8,1972,8,24,9,15,9,1978,                  # 1960
 9,15,9,15,30,30,9,1986,9,15,30,15,10,1992,30,15,30,1996,9,1998,          # 1980
 30,16,30,2002,9,9,30,22,9,40,9,2010,30,28,30,30,31,2016,8,15,            # 2000
 27,42,8,15,23,30,21,2026,8,2028,8,30,15,30,13,15,11,30,8,2038,           # 2020
 8,15,8,30,8,30,8,22,2047,15,8,15,8,2052,8,15,8,16,10,28,                 # 2040
 8,15,9,2062,15,15,8,15,8,2068,8,18,8,15,9,24,8,30,30,15,                 # 2060
 30,2080,8,2082,8,15,8,2086,10,2088,12,15,8,30,16,30,18,15,8,2098,        # 2080
 22,36,24,15,26,30,28,42,30,30,30,2110,15,2112,30,15,9,28,30,24,          # 2100
 30,15,10,15,30,18,30,16,15,2128,30,2130,8,26,9,15,30,2136,30,15,         # 2120
 9,2140,9,2142,31,15,9,18,9,15,9,15,9,2152,10,15,12,15,9,16,              # 2140
 15,2160,9,15,9,14,9,15,9,15,10,14,12,40,9,15,16,15,9,2178,               # 2160
 8,15,9,36,9,15,9,2186,9,15,9,23,15,15,8,15,9,2196,12,15,                 # 2180
 9,30,30,2202,8,15,9,2206,15,2208,8,30,10,2212,12,15,8,30,16,30,          # 2200
 18,2220,8,30,22,24,24,16,26,30,28,30,30,30,30,15,10,2236,30,2238,        # 2220
 16,30,30,2242,30,15,8,15,30,22,30,2250,8,18,30,15,15,36,8,15,            # 2240
 30,15,30,30,30,30,9,2266,30,2268,8,15,31,2272,10,30,12,15,8,42,          # 2260
 16,2280,18,15,8,30,22,2286,24,15,26,30,28,2292,30,30,30,2296,9,30,       # 2280
 30,15,9,46,30,30,30,15,9,2308,30,2310,30,22,9,20,30,15,9,15,             # 2300
 15,15,30,22,30,15,9,30,28,16,30,15,9,2332,30,15,31,15,9,2338,            # 2320
 8,2340,8,10,9,15,8,2346,8,28,8,2350,15,12,8,15,9,2356,9,10,              # 2340
 8,15,8,16,8,9,8,10,36,22,10,2370,8,10,8,18,26,2376,8,10,                 # 2360
 8,2380,8,2382,15,15,8,15,8,2388,8,15,8,2392,8,42,10,15,13,2398,          # 2380
 15,2400,8,26,8,15,9,28,7,15,7,2410,8,18,17,15,15,2416,7,40,              # 2400
 8,15,8,2422,14,24,12,15,8,15,16,15,18,15,8,15,9,2436,9,15,               # 2420
 9,2440,10,15,10,15,10,2446,15,30,30,15,9,27,9,30,9,15,9,2458,            # 2440
 10,30,12,15,15,30,16,2466,18,15,9,30,22,2472,24,15,26,2476,28,36,        # 2460
 30,30,30,15,12,30,30,15,9,30,30,46,30,15,9,15,30,30,30,28,               # 2480
 8,40,30,2502,8,15,9,22,30,15,30,30,30,30,9,15,30,30,8,15,                # 2500
 30,2520,30,30,12,24,9,30,31,30,18,2530,9,30,22,15,24,42,26,2538,         # 2520
 28,30,30,2542,30,15,9,30,30,2548,9,2550,30,30,30,15,9,2556,30,30,        # 2540
 30,30,9,28,30,15,10,16,9,23,30,15,30,30,30,30,15,15,30,2578,             # 2560
 9,28,30,30,30,30,12,12,12,30,30,2590,31,2592,8,30,22,48,24,22,           # 2580
 26,30,28,30,30,30,30,9,15,2608,30,15,9,30,30,30,30,2616,8,26,            # 2600
 30,2620,30,42,40,30,30,36,8,15,8,24,30,2632,30,15,8,30,8,16,             # 2620
 30,18,8,15,30,15,30,2646,28,15,8,15,30,15,30,15,31,2656,10,2658,         # 2640
 8,15,9,2662,9,15,9,15,7,16,9,2670,15,15,8,24,8,2676,8,15,                # 2660
 9,15,8,2682,9,15,8,2686,15,2688,8,15,10,2692,8,15,8,15,9,2698,           # 2680
 9,36,8,15,15,15,10,2706,8,15,10,2710,9,2712,8,15,10,15,10,2718,          # 2700
 31,15,9,15,9,24,10,26,10,2728,10,2730,9,15,10,15,15,15,8,15,             # 2720
 8,2740,8,15,9,15,8,40,9,2748,8,15,42,2752,9,15,8,15,9,30,                # 2740
 30,15,8,15,9,30,7,2766,15,30,10,30,12,46,8,30,16,2776,18,15,             # 2760
 9,30,22,22,24,15,26,30,28,2788,30,2790,30,15,9,30,30,2796,9,30,          # 2780
 30,2800,30,2802,9,15,30,30,30,2808,8,30,30,28,9,15,15,30,30,2818,        # 2800
 30,15,8,30,9,24,30,15,8,18,30,18,30,2832,9,15,9,2836,30,23,              # 2820
 30,15,30,2842,8,15,8,15,31,15,10,2850,8,15,9,15,8,2856,8,15,             # 2840
 8,2860,29,13,29,15,9,46,29,18,29,15,8,16,29,22,8,15,8,2878,              # 2860
 29,42,29,15,9,29,9,2886,29,26,8,48,29,15,29,15,15,2896,9,15,             # 2880
 29,15,30,2902,8,15,8,15,8,2908,10,40,31,15,9,15,8,2916,9,15,             # 2900
 8,22,21,36,9,18,9,2926,15,28,9,15,10,15,12,15,9,15,16,2938,              # 2920
 18,16,9,26,22,15,9,15,9,15,9,15,9,2952,9,15,9,2956,9,15,                 # 2940
 15,15,9,2962,9,15,9,15,9,2968,9,2970,9,15,10,15,15,15,12,15,             # 2960
 9,15,10,18,9,15,9,28,9,48,8,15,15,40,9,15,9,36,9,2998,                   # 2980
 9,3000,9,15,10,15,9,30,46,15,9,3010,9,30,8,15,10,30,10,3018,             # 3000
 12,15,9,3022,16,30,18,15,9,30,22,15,24,15,26,30,28,3036,30,30,           # 3020
 31,3040,9,30,30,15,9,30,30,3048,30,26,9,42,30,30,30,30,9,30,             # 3040
 30,3060,9,15,9,30,30,3066,30,15,9,36,15,30,30,15,8,26,30,3078,           # 3060
 30,15,9,3082,9,18,30,15,30,3088,30,15,9,15,10,15,30,18,9,15,             # 3080
 9,15,9,28,31,15,9,25,9,3108,8,15,9,15,8,15,8,15,9,3118,                  # 3100
 15,3120,8,15,9,3124,8,52,8,15,9,30,30,15,8,15,48,3136,9,42,              # 3120
 8,30,10,30,12,15,9,30,16,46,18,22,15,30,22,15,24,15,26,30,               # 3140
 28,30,30,3162,30,15,9,3166,30,3168,9,30,30,30,30,24,23,15,30,30,         # 3160
 30,3180,10,30,30,15,10,3186,12,30,30,3190,30,30,30,30,8,30,30,30,        # 3180
 24,30,30,3202,30,30,12,24,9,3208,30,30,30,18,30,30,22,3216,24,15,        # 3200
 30,3220,28,30,30,30,30,15,30,3228,30,15,31,52,30,30,30,15,9,40,          # 3220
 30,30,30,30,9,30,30,16,15,15,10,3250,30,3252,30,15,9,3256,9,3258,        # 3240
 30,15,10,30,30,30,30,26,10,26,9,3270,30,15,30,24,30,28,10,15,            # 3260
 15,16,30,48,9,15,10,18,28,15,30,15,9,36,30,15,31,15,9,3298,              # 3280
 10,3300,10,15,10,15,10,3306,10,15,9,15,15,3312,9,15,9,30,30,3318,        # 3300
 9,40,9,3322,9,23,9,30,14,3328,12,3330,10,30,16,30,18,46,9,30,            # 3320
 22,15,24,3342,26,30,28,3346,30,30,30,15,10,30,30,13,10,30,30,3358,       # 3340
 30,3360,10,15,30,30,30,30,12,30,30,3370,10,3372,10,30,30,15,30,30,       # 3360
 30,30,9,30,30,30,9,30,30,3388,30,3390,52,30,10,30,30,42,30,24,           # 3380
 30,39,22,40,24,23,30,3406,28,30,30,30,30,3412,30,30,30,15,30,30,         # 3400
 30,30,30,15,31,24,30,30,30,30,25,46,30,3432,9,15,10,30,30,18,            # 3420
 30,15,13,30,10,30,30,15,22,3448,30,30,30,13,24,30,26,3456,30,15,         # 3440
 30,3460,30,3462,9,15,9,3466,30,3468,9,10,15,22,10,24,30,18,9,48,         # 3460
 30,3480,30,42,10,15,30,39,31,15,9,3490,9,11,10,13,10,15,12,3498,         # 3480
 9,15,10,30,30,11,10,15,9,30,10,3510,9,30,10,30,12,3516,9,30,             # 3500
 26,30,18,15,12,30,22,3526,24,3528,26,30,28,3532,30,30,30,26,10,3538,     # 3520
 30,3540,11,30,30,30,30,3546,11,15,30,52,30,30,10,30,30,3556,10,3558,     # 3540
 11,30,30,12,30,12,11,30,15,42,30,3570,11,30,30,30,30,48,10,30,           # 3560
 10,3580,30,3582,30,30,30,16,10,36,10,15,30,3592,11,15,11,18,10,58,       # 3580
 30,15,10,13,30,15,30,3606,9,15,30,22,30,3612,9,15,31,3616,9,15,          # 3600
 10,15,9,3622,10,28,11,15,9,25,11,3630,15,15,10,15,10,3636,9,15,          # 3620
 9,15,8,3642,11,15,9,15,26,40,10,15,9,15,12,15,9,25,9,3658,               # 3640
 11,15,11,15,15,15,10,18,9,15,9,3670,10,3672,10,15,9,3676,8,21,           # 3660
 15,15,10,28,27,15,10,24,9,15,10,3690,10,18,10,16,15,3696,10,26,          # 3680
 16,3700,18,15,24,15,22,15,24,3708,26,15,28,46,10,15,10,15,9,3718,        # 3700
 10,3720,10,15,11,24,9,3726,15,15,9,15,10,3732,10,15,9,36,9,3738,         # 3720
 9,15,10,18,15,39,10,15,9,22,10,30,30,26,9,15,10,30,12,15,                # 3740
 15,3760,10,52,12,15,10,3766,16,3768,18,15,9,30,22,24,58,15,26,3778,      # 3760
 28,30,30,30,30,15,10,30,30,15,10,30,30,3792,30,15,10,3796,30,30,         # 3780
 30,30,10,3802,30,15,9,46,31,30,30,36,30,15,9,30,9,30,30,15,              # 3800
 10,3820,30,3822,30,15,10,42,10,30,30,15,30,3832,30,15,10,15,10,15,       # 3820
 30,30,10,15,10,26,10,3846,30,15,9,3850,30,3852,30,15,15,15,30,16,        # 3840
 30,15,10,3862,30,15,9,15,9,52,9,48,31,15,10,30,30,3876,10,15,            # 3860
 10,3880,9,15,10,30,10,30,15,3888,10,30,16,30,18,15,9,30,22,15,           # 3880
 24,48,26,30,60,30,30,3906,30,15,9,3910,30,15,11,30,30,3916,30,3918,      # 3900
 15,15,30,3922,30,30,9,30,30,3928,9,3930,9,30,30,15,30,30,30,30,          # 3920
 9,30,30,3942,9,30,30,3946,30,30,12,30,15,58,30,30,30,30,30,36,           # 3940
 26,40,24,15,30,30,28,3966,30,48,30,28,30,36,30,24,30,40,30,30,           # 3960
 30,18,30,16,30,30,30,30,30,3988,30,22,10,24,10,30,30,28,30,30,           # 3980
 31,4000,10,4002,30,30,10,4006,30,30,30,30,9,4012,9,30,30,30,30,4018,     # 4000
 30,4020,9,26,9,24,30,4026,9,30,9,30,30,36,30,30,9,26,30,30,              # 4020
 30,30,10,20,30,18,30,30,15,4048,30,4050,18,15,9,15,28,4056,30,15,        # 4040
 26,30,30,16,31,30,10,48,27,30,9,30,10,4072,21,30,19,30,16,4078,          # 4060
 18,30,10,30,22,15,24,60,26,30,28,4090,30,4092,30,30,4095,30,30,4098,     # 4080
 9,30,30,30,30,15,9,15,30,30,30,4110,15,30,30,15,10,22,10,30,             # 4100
 30,15,30,15,11,30,9,4126,30,4128,10,30,30,4132,30,15,11,30,10,4138,      # 4120
 30,40,30,30,30,15,10,15,10,15,30,30,9,4152,11,30,9,4156,30,4158,         # 4140
 15,30,30,22,30,15,29,24,30,22,30,42,29,15,30,24,29,4176,10,15,           # 4160
 10,36,30,46,29,15,30,52,30,58,29,15,31,15,29,15,29,15,10,15,             # 4180
 12,4200,29,15,29,15,29,15,15,15,10,4210,29,15,9,15,9,4216,10,4218,       # 4200
 29,15,9,40,29,24,29,15,10,4228,29,4230,29,15,10,15,29,18,13,26,          # 4220
 15,4240,10,4242,30,15,9,30,30,15,12,15,9,4252,13,15,31,30,10,4258,       # 4240
 12,4260,10,30,16,30,18,42,9,30,22,4270,24,4272,26,30,28,30,30,30,        # 4260
 30,15,10,4282,30,15,9,30,63,4288,30,15,10,52,30,30,30,4296,9,30,         # 4280
 30,15,10,15,15,30,30,58,30,30,30,30,9,30,30,30,9,30,30,30,               # 4300
 30,30,12,30,10,30,30,4326,30,30,30,60,22,15,24,15,30,4336,28,4338,       # 4320
 30,30,30,42,30,30,30,30,30,4348,30,30,30,30,30,28,30,4356,30,30,         # 4340
 30,48,30,4362,13,18,13,30,30,16,30,15,30,4372,30,30,30,15,30,30,         # 4360
 30,30,30,15,31,30,12,40,30,15,30,4390,30,22,13,15,13,4396,30,52,         # 4380
 15,26,12,30,13,30,30,15,13,4408,30,15,30,15,10,30,30,30,30,15,           # 4400
 12,4420,30,4422,13,15,13,20,12,42,30,15,15,15,30,15,30,30,12,22,         # 4420
 30,4440,11,15,13,15,30,4446,31,15,10,4450,12,60,13,15,12,4456,13,15,     # 4440
 13,15,13,4462,15,15,11,15,10,40,12,16,13,15,13,24,13,36,13,15,           # 4460
 16,4480,10,4482,10,15,12,15,13,4488,13,15,10,4492,13,15,15,15,10,25,     # 4480
 10,15,10,15,10,15,12,4506,13,26,13,15,15,4512,10,15,10,4516,10,4518,     # 4500
 10,15,12,4522,13,24,10,15,15,15,11,22,10,15,10,15,10,15,10,15,           # 4520
 12,18,13,15,63,15,10,4546,10,4548,10,15,10,28,10,15,12,15,12,46,         # 4540
 15,4560,11,26,11,15,10,4566,10,15,12,15,12,16,13,15,31,22,11,18,         # 4560
 10,15,10,4582,10,15,10,15,12,15,13,4590,15,15,10,15,10,4596,12,15,       # 4580
 10,42,10,4602,12,15,9,16,15,15,13,15,11,15,9,15,9,18,10,30,              # 4600
 30,4620,12,15,16,36,15,15,13,30,15,30,15,40,15,30,16,4636,18,4638,       # 4620
 31,30,22,4642,24,15,26,30,28,4648,30,4650,30,15,15,30,30,4656,12,30,     # 4640
 30,58,30,4662,14,15,30,30,30,30,14,30,63,4672,12,15,14,30,30,4678,       # 4660
 30,30,30,30,14,30,30,42,15,30,30,4690,30,30,14,30,15,30,30,36,           # 4680
 35,30,30,4702,22,15,24,15,30,30,28,30,30,30,30,30,30,52,30,30,           # 4700
 30,4720,30,4722,30,30,30,30,30,4728,30,31,30,4732,30,15,36,30,12,30,     # 4720
 30,15,30,15,30,30,30,46,30,15,30,4750,30,48,30,15,30,66,30,4758,         # 4740
 30,15,30,30,30,15,13,15,31,18,30,30,11,15,10,30,10,39,30,58,             # 4760
 15,30,30,4782,30,15,12,4786,30,4788,30,15,10,4792,30,15,14,15,15,4798,   # 4780
 15,4800,30,15,10,15,30,24,30,30,10,16,30,4812,14,15,15,4816,30,60,       # 4800
 30,15,10,22,28,24,12,15,12,15,30,4830,31,26,12,15,10,23,10,15,           # 4820
 10,46,11,28,12,15,15,36,15,15,11,15,10,22,10,15,11,15,10,42,             # 4840
 11,4860,14,15,18,17,12,30,30,15,10,4870,11,30,11,15,12,4876,11,30,       # 4860
 15,16,10,30,16,30,18,26,10,4888,22,66,24,15,26,30,28,58,30,30,           # 4880
 30,28,12,4902,30,15,10,30,30,4908,30,15,15,4912,30,30,30,30,10,4918,     # 4900
 30,15,11,15,10,30,30,15,30,15,12,4930,11,4932,30,15,11,4936,30,30,       # 4920
 30,60,10,4942,15,30,30,15,30,48,30,4950,10,15,10,15,30,4956,10,15,       # 4940
 15,40,11,30,30,15,12,4966,30,4968,30,15,10,4972,30,30,30,15,12,15,       # 4960
 30,16,10,15,11,30,10,4986,30,15,10,15,30,4992,30,30,10,18,30,4998,       # 4980
 11,15,10,5002,30,18,30,15,15,5008,10,5010,11,15,10,15,30,28,30,15,       # 5000
 10,5020,10,5022,31,15,10,15,10,46,10,15,9,15,10,15,10,15,10,5038,        # 5020
 15,5040,10,15,11,15,10,48,9,15,10,5050,10,30,30,15,63,15,10,5058,        # 5040
 11,15,10,60,10,30,12,15,10,36,16,30,18,15,10,30,22,5076,24,15,           # 5060
 26,5080,28,30,30,30,30,5086,31,30,30,15,12,30,30,30,30,15,10,5098,       # 5080
 30,5100,30,30,15,30,30,5106,11,15,10,30,30,5112,30,15,10,30,10,5118,     # 5100
 30,39,10,46,30,40,30,15,10,30,13,30,30,15,30,30,30,15,10,15,             # 5120
 11,52,30,36,11,15,13,5146,13,45,30,15,31,5152,30,15,30,26,10,30,         # 5140
 30,30,30,15,12,15,30,5166,15,15,15,5170,15,30,30,15,15,30,30,5178,       # 5160
 30,30,15,70,63,30,15,30,15,5188,30,28,30,30,16,30,18,5196,15,30,         # 5180
 22,15,30,42,30,30,28,40,39,5208,30,36,15,30,30,15,31,30,30,30,           # 5200
 30,22,15,15,30,30,30,5226,15,30,30,5230,24,5232,26,30,30,5236,30,31,     # 5220
 30,30,13,48,36,30,15,30,40,30,30,58,15,30,15,30,30,30,30,30,             # 5240
 30,5260,22,18,24,15,30,30,28,30,30,30,30,5272,30,30,30,30,30,5278,       # 5260
 31,5280,30,30,30,30,30,30,30,30,30,30,30,66,15,30,15,5296,30,16,         # 5280
 30,15,30,5302,30,30,30,15,30,5308,30,46,63,30,30,30,30,30,30,26,         # 5300
 30,30,30,5322,15,18,30,16,30,5328,12,16,10,5332,30,30,30,15,15,30,       # 5320
 30,48,30,15,31,30,30,5346,30,15,10,5350,30,52,11,15,15,30,15,30,         # 5340
 30,15,12,30,30,30,30,30,10,30,30,40,15,30,15,42,30,30,30,30,             # 5360
 16,5380,18,15,14,30,22,5386,30,18,30,30,28,5392,30,30,30,15,12,5398,     # 5380
 30,15,30,30,30,30,30,5406,31,15,30,30,30,5412,9,30,30,5416,12,5418,      # 5400
 11,30,30,15,30,15,13,66,12,60,30,5430,11,30,30,30,30,5436,15,30,         # 5420
 40,5440,30,5442,30,30,30,15,11,5448,11,15,30,30,15,15,15,30,10,52,       # 5440
 30,42,41,30,30,38,30,15,11,30,30,5470,30,30,12,16,30,5476,16,5478,       # 5460
 18,30,10,5482,30,18,24,15,30,30,30,30,30,31,30,30,38,22,36,30,           # 5480
 30,5500,40,5502,42,30,10,5506,14,15,12,24,30,36,30,15,10,15,10,5518,     # 5500
 30,5520,10,15,10,15,30,5526,10,15,30,5530,30,15,10,15,31,48,10,28,       # 5520
 10,15,9,25,9,15,10,15,12,30,30,15,15,15,11,30,10,5556,10,30,             # 5540
 10,66,12,5562,9,30,16,30,18,5568,10,30,22,5572,24,24,26,30,28,30,        # 5560
 30,5580,30,15,15,30,30,36,12,30,30,5590,30,15,13,15,30,30,30,30,         # 5580
 15,30,30,15,11,15,10,30,30,70,30,30,30,30,10,30,30,40,12,30,             # 5600
 30,30,30,5622,12,30,11,30,30,30,30,30,30,42,22,15,24,15,30,5638,         # 5620
 28,5640,30,30,30,30,30,5646,30,30,30,5650,30,5652,30,30,30,5656,30,5658, # 5640
 30,30,30,30,30,15,10,30,10,5668,30,52,30,15,30,30,30,30,30,15,           # 5660
 30,30,30,5682,30,30,30,46,30,5688,30,30,30,5692,30,15,63,30,30,40,       # 5680
 30,5700,10,15,11,30,30,30,30,18,11,5710,30,28,30,15,30,5716,30,30,       # 5700
 30,15,30,58,30,24,10,15,31,30,10,30,30,15,11,15,30,5736,30,30,           # 5720
 11,5740,30,5742,15,15,10,30,30,5748,30,70,11,30,11,15,14,15,11,30,       # 5740
 30,30,30,15,11,15,11,72,30,15,11,28,11,22,30,15,16,52,30,5778,           # 5760
 30,15,11,5782,30,15,10,15,10,15,30,5790,31,15,10,15,11,15,10,15,         # 5780
 11,5800,11,15,9,15,11,5806,15,39,10,15,11,5812,12,15,10,15,10,15,        # 5800
 10,5820,13,15,63,24,10,5826,11,15,10,16,10,18,10,15,10,15,13,5838,       # 5820
 15,15,10,5842,10,15,10,15,11,5848,10,5850,10,15,12,15,15,5856,10,15,     # 5840
 10,5860,10,27,11,15,10,5866,10,5868,11,15,15,15,13,46,11,15,10,5878,     # 5860
 10,5880,10,15,10,15,12,15,22,21,13,42,13,70,11,15,13,5896,13,16,         # 5880
 13,15,13,5902,15,16,13,18,12,18,13,22,13,72,13,15,13,60,13,15,           # 5900
 15,30,30,5922,13,15,13,5926,13,48,13,30,13,30,13,15,15,30,16,5938,       # 5920
 18,15,10,30,22,16,24,18,26,30,28,30,30,5952,30,15,12,30,30,58,           # 5940
 13,30,30,66,30,15,13,15,30,46,45,30,11,42,30,24,13,42,11,36,             # 5960
 30,5980,30,30,30,30,16,5986,30,52,13,30,30,30,30,30,26,30,28,30,         # 5980
 30,31,30,30,30,30,36,6006,24,15,40,6010,42,30,30,30,46,30,30,30,         # 6000
 30,30,30,30,30,30,30,30,30,6028,30,45,30,30,30,30,30,6036,13,30,         # 6020
 13,30,30,6042,30,15,30,6046,30,30,30,15,30,6052,30,30,30,30,30,72,       # 6040
 30,30,30,30,30,30,30,6066,12,30,30,30,30,6072,12,24,12,58,30,6078,       # 6060
 46,30,10,30,30,15,30,24,30,6088,30,6090,30,15,30,15,30,15,13,15,         # 6080
 30,6100,30,30,30,15,12,30,30,40,30,30,31,6112,30,30,11,30,10,30,         # 6100
 30,6120,30,30,16,48,18,15,15,45,22,6130,30,6132,30,30,28,30,30,30,       # 6120
 30,15,12,6142,30,30,30,30,30,30,30,6150,30,15,30,30,30,46,11,30,         # 6140
 30,60,30,6162,30,30,30,15,30,30,30,30,11,6172,30,30,31,45,30,36,         # 6160
 30,30,12,30,11,30,30,30,30,30,30,40,22,15,24,15,30,6196,28,6198,         # 6180
 30,30,30,6202,30,30,30,30,63,30,30,6210,30,30,30,30,30,6216,30,30,       # 6200
 30,6220,30,48,47,30,11,44,30,6228,30,15,30,38,30,36,30,15,30,30,         # 6220
 30,6240,30,30,30,30,30,6246,30,30,30,30,30,36,30,31,30,6256,30,30,       # 6240
 36,15,15,6262,44,30,42,30,15,6268,46,6270,48,30,30,30,30,6276,30,16,     # 6260
 30,15,30,60,15,15,30,6286,30,30,30,26,15,15,30,30,30,30,30,6298,         # 6280
 30,6300,15,15,31,30,30,30,30,15,15,6310,15,58,15,15,15,6316,30,70,       # 6300
 30,15,15,6322,15,39,30,16,15,6328,15,30,30,15,15,30,30,6336,30,15,       # 6320
 15,16,30,6342,15,15,15,15,30,18,30,15,15,6352,15,18,15,15,15,6358,       # 6340
 30,6360,30,15,15,15,30,6366,31,15,15,22,15,6372,15,15,15,15,15,6378,     # 6360
 15,15,15,15,15,15,15,15,15,6388,15,70,15,15,15,15,15,6396,15,78,         # 6380
 24,36,15,18,11,15,15,42,15,48,15,15,15,52,15,15,15,16,15,48,             # 6400
 15,6420,15,22,15,24,15,6426,15,15,15,58,15,15,13,15,15,40,10,46,         # 6420
 15,15,15,16,15,15,15,15,15,6448,15,6450,11,26,13,16,15,15,15,15,         # 6440
 15,15,15,22,63,15,15,28,15,6468,12,15,15,6472,15,15,15,15,15,15,         # 6460
 15,6480,15,15,13,15,13,15,15,15,15,6490,15,42,15,15,31,72,13,66,         # 6480
 15,15,12,15,11,15,15,26,15,22,15,16,15,15,13,15,15,18,12,16,             # 6500
 11,6520,15,15,15,15,15,60,24,6528,13,15,15,46,11,17,12,15,15,15,         # 6520
 15,30,30,15,15,15,15,6546,11,15,14,6550,11,6552,12,15,15,78,16,30,       # 6540
 31,6560,15,6562,22,15,24,16,26,6568,28,6570,30,30,30,24,15,6576,30,15,   # 6560
 11,6580,30,30,30,15,11,15,30,30,30,30,63,30,30,15,11,15,11,6598,         # 6580
 30,15,30,15,11,30,10,6606,30,15,10,30,30,30,30,16,11,30,11,6618,         # 6600
 30,15,30,36,30,52,11,15,11,15,30,30,11,15,11,30,11,6636,30,15,           # 6620
 15,30,30,15,30,15,11,30,30,60,30,15,11,6652,30,15,15,15,11,6658,         # 6640
 11,6660,30,15,11,15,30,58,30,30,12,15,30,6672,12,15,11,30,30,6678,       # 6660
 30,15,12,40,12,15,14,15,18,6688,30,6690,30,15,11,15,12,36,30,15,         # 6680
 14,6700,12,6702,30,16,11,30,30,6708,30,15,11,48,30,15,11,15,14,6718,     # 6700
 30,30,30,80,11,24,12,23,11,15,11,52,51,6732,30,48,15,6736,30,22,         # 6720
 30,42,11,40,12,15,11,15,16,16,18,42,31,30,22,28,24,28,26,15,             # 6740
 28,6760,30,6762,12,15,10,66,36,17,11,15,40,15,42,24,15,26,46,6778,       # 6760
 48,6780,15,15,52,15,15,17,12,15,13,6790,15,6792,15,15,15,15,15,15,       # 6780
 15,15,15,6802,15,17,15,15,15,23,15,48,15,15,15,15,15,16,15,15,           # 6800
 15,18,15,6822,15,24,15,6826,15,6828,15,15,15,6832,15,15,15,15,15,15,     # 6820
 15,6840,15,15,15,15,15,40,63,21,15,15,15,15,15,15,15,6856,15,6858,       # 6840
 15,15,15,6862,15,15,15,15,15,6868,15,6870,15,16,15,15,15,15,15,15,       # 6860
 31,15,15,6882,15,15,15,70,15,6888,15,15,15,60,15,15,15,15,15,6898,       # 6880
 15,66,15,15,15,15,15,6906,15,15,15,6910,26,30,30,15,15,6916,15,30,       # 6900
 15,16,15,30,15,30,15,15,15,40,16,30,18,15,15,30,22,24,24,26,             # 6920
 26,30,28,52,31,30,30,6946,15,6948,30,15,15,30,30,30,30,15,15,6958,       # 6940
 30,6960,30,30,15,30,30,6966,15,16,15,6970,30,18,30,15,63,6976,15,30,     # 6960
 30,15,15,6982,30,30,30,15,15,30,15,6990,30,15,30,30,30,6996,15,15,       # 6980
 15,7000,30,46,15,15,15,30,15,42,30,15,15,7012,30,15,30,15,15,7018,       # 7000
 30,30,30,15,15,24,30,7026,15,15,15,78,15,30,30,15,15,30,30,7038,         # 7020
 30,30,15,7042,30,30,15,30,15,52,30,30,30,30,16,30,18,7056,15,30,         # 7040
 22,30,30,30,30,30,28,36,30,7068,30,15,16,30,30,30,30,30,30,7078,         # 7060
 30,72,30,15,30,30,30,30,15,30,30,15,30,40,30,30,30,46,30,39,             # 7080
 30,30,15,7102,30,30,30,30,30,7108,30,30,30,30,15,30,30,30,30,30,         # 7100
 30,7120,22,16,30,15,30,7126,28,7128,30,30,30,30,30,30,31,30,30,58,       # 7120
 30,36,30,30,30,30,30,30,30,30,30,7150,30,22,13,30,15,30,30,7158,         # 7140
 30,16,30,30,30,30,30,15,30,66,30,70,30,30,30,30,30,7176,30,30,           # 7160
 30,42,30,15,15,30,30,7186,30,30,13,15,13,7192,30,30,30,30,15,30,         # 7180
 30,18,30,30,30,30,30,7206,30,80,30,7210,30,7212,15,15,30,30,30,7218,     # 7200
 30,15,10,30,30,30,30,30,30,7228,30,30,63,30,30,30,30,7236,30,30,         # 7220
 16,30,18,7242,14,30,22,7246,30,30,30,30,28,7252,30,30,30,15,13,30,       # 7240
 30,52,30,30,31,30,30,42,30,15,30,30,30,30,13,30,30,18,30,30,             # 7260
 30,30,30,7282,30,15,11,30,12,36,30,30,30,30,30,30,30,7296,30,30,         # 7280
 15,48,30,66,30,30,30,7306,15,7308,30,16,30,70,13,15,13,30,15,30,         # 7300
 30,7320,30,30,30,24,30,16,31,30,30,7330,30,7332,15,15,30,15,15,40,       # 7320
 15,30,15,30,30,15,15,15,30,7348,30,7350,15,15,30,30,15,15,15,30,         # 7340
 30,30,30,36,15,30,15,52,15,7368,15,30,30,72,30,58,15,15,15,46,           # 7360
 30,60,15,30,15,30,30,82,15,30,30,30,30,7392,15,15,30,16,15,48,           # 7380
 24,15,30,30,30,15,15,15,15,30,30,7410,15,15,30,30,30,7416,15,30,         # 7400
 30,40,30,15,28,30,16,30,18,16,15,30,22,7432,30,20,26,30,28,42,           # 7420
 30,30,30,18,15,30,30,22,15,30,30,7450,30,28,15,15,31,7456,30,7458,       # 7440
 15,30,30,16,15,15,15,30,30,15,30,30,30,30,15,30,30,7476,15,30,           # 7460
 30,7480,30,30,15,30,15,7486,30,7488,30,30,30,58,57,15,24,54,30,7498,     # 7480
 28,30,30,48,30,46,30,7506,30,30,30,30,30,30,30,36,30,7516,30,72,         # 7500
 30,30,30,7522,30,31,15,30,15,7528,36,16,30,30,40,30,42,7536,30,30,       # 7520
 46,7540,48,30,30,30,52,7546,30,7548,30,30,58,30,30,30,22,30,30,7558,     # 7540
 30,7560,28,30,30,30,30,30,30,30,30,66,30,7572,30,30,30,7576,30,30,       # 7560
 30,30,30,7582,30,30,30,26,30,7588,30,7590,30,15,30,16,30,70,30,30,       # 7580
 30,30,30,7602,30,30,30,7606,30,30,30,30,30,30,30,39,58,30,13,30,         # 7600
 30,7620,30,30,15,60,15,30,30,30,30,30,30,30,30,15,30,30,30,7638,         # 7620
 30,30,30,7642,30,15,30,15,31,7648,30,30,30,30,30,15,15,15,30,30,         # 7640
 30,46,30,78,30,30,15,30,30,7668,30,30,30,7672,14,30,15,15,15,30,         # 7660
 15,7680,30,30,30,15,15,7686,15,15,30,7690,15,48,30,30,30,42,30,7698,     # 7680
 30,30,30,7702,30,15,30,15,15,15,30,17,31,30,30,15,15,7716,15,15,         # 7700
 14,15,14,7722,30,30,30,7726,15,58,30,30,30,15,15,30,15,15,14,70,         # 7720
 13,7740,15,30,63,30,15,60,59,15,15,56,15,7752,14,15,30,7756,17,7758,     # 7740
 30,15,30,16,16,17,30,15,28,38,22,36,30,15,30,24,31,30,30,31,             # 7760
 14,30,30,42,36,15,14,30,40,7788,42,30,15,7792,46,15,48,30,16,30,         # 7780
 56,28,15,30,22,15,58,36,60,30,28,72,30,30,30,15,15,7816,30,16,           # 7800
 15,30,30,7822,30,24,14,15,30,7828,30,40,15,30,30,16,15,16,13,30,         # 7820
 30,7840,30,15,14,30,15,30,30,46,15,30,30,7852,30,15,15,80,13,30,         # 7840
 30,23,30,30,30,15,15,7866,15,15,30,30,15,7872,13,30,15,7876,30,7878,     # 7860
 15,30,30,7882,30,15,15,30,30,30,30,15,15,15,30,15,15,52,15,30,           # 7880
 15,7900,30,15,18,15,30,7906,30,30,15,26,30,40,15,16,15,30,30,7918,       # 7900
 30,7920,15,30,15,24,15,7926,15,30,30,30,30,7932,15,15,30,7936,30,16,     # 7920
 15,30,30,46,30,15,30,30,30,7948,30,7950,30,16,30,18,15,72,30,22,         # 7940
 30,30,30,7962,30,28,30,30,31,30,15,15,30,30,30,15,30,30,30,78,           # 7960
 30,22,15,30,30,30,30,48,30,30,22,60,30,7992,30,30,28,30,30,30,           # 7980
 63,30,30,52,30,15,30,30,30,8008,30,8010,30,18,30,30,30,8016,30,30,       # 8000
 30,15,30,70,30,30,30,22,30,15,30,30,31,30,30,15,30,30,30,8038,           # 8020
 30,15,30,30,30,30,30,15,30,30,30,82,15,8052,30,15,30,30,15,8058,         # 8040
 15,30,30,30,30,15,15,30,30,8068,30,15,30,30,30,30,30,40,30,15,           # 8060
 30,8080,15,58,30,30,30,8086,30,8088,15,15,30,8092,30,30,31,18,30,30,     # 8080
 15,8100,30,30,30,30,30,66,15,30,15,8110,15,25,15,30,30,8116,30,22,       # 8100
 15,15,15,8122,30,15,15,30,63,62,30,46,59,30,30,30,30,78,53,15,           # 8120
 51,17,15,16,30,27,30,8146,30,28,41,22,39,30,30,26,30,28,33,40,           # 8140
 31,8160,29,30,30,36,30,8166,23,40,21,8170,18,15,17,46,22,48,30,8178,     # 8160
 26,80,28,48,30,30,30,58,26,60,30,8190,8191,30,30,30,30,15,15,24,         # 8180
 30,58,30,30,15,30,30,28,30,8208,30,30,30,42,30,22,15,30,30,8218,         # 8200
 30,8220,15,30,31,30,30,18,15,30,15,8230,30,8232,30,30,30,8236,15,57,     # 8220
 15,15,30,8242,15,15,15,30,15,72,30,36,15,30,30,15,62,22,15,30,           # 8240
 30,30,30,8262,15,15,30,18,15,8268,15,30,15,8272,30,24,15,15,30,30,       # 8260
 30,48,14,15,30,30,15,8286,15,30,30,8290,30,8292,15,30,15,8296,15,42,     # 8280
 15,30,30,30,30,16,15,15,15,15,30,8310,15,30,15,30,30,8316,15,30,         # 8300
 30,52,30,15,15,17,30,25,15,8328,15,15,30,30,30,15,15,15,14,30,           # 8320
 30,18,15,80,30,30,30,16,15,30,30,30,30,8352,14,30,16,60,18,15,           # 8340
 14,57,22,8362,30,30,26,30,28,8368,30,30,30,30,15,66,30,8376,30,30,       # 8360
 30,30,30,82,63,30,30,8386,30,8388,15,30,30,22,30,16,30,30,30,36,         # 8380
 30,30,30,30,30,30,30,30,15,30,30,30,30,46,15,30,31,30,30,8418,           # 8400
 30,30,30,8422,22,24,24,15,30,8428,28,8430,30,30,30,30,30,30,30,30,       # 8420
 30,30,30,8442,30,30,30,8446,30,30,30,30,30,78,30,15,15,30,15,30,         # 8440
 30,8460,30,30,30,30,30,8466,30,16,30,42,30,36,30,30,30,48,30,60,         # 8460
 30,30,30,30,30,15,22,30,30,30,30,30,28,15,29,30,30,30,30,30,             # 8480
 29,8500,30,15,30,30,30,46,30,66,65,16,30,8512,30,15,29,15,30,56,         # 8500
 30,8520,30,15,29,15,30,8526,30,30,30,44,30,42,29,30,30,8536,30,8538,     # 8520
 30,31,29,8542,29,30,36,30,15,82,40,30,42,15,15,20,46,42,48,30,           # 8540
 29,30,52,8562,30,30,30,30,58,30,60,30,30,8572,30,24,66,30,30,28,         # 8560
 30,8580,30,15,29,22,15,30,30,18,30,70,30,30,30,30,30,8596,30,8598,       # 8580
 30,15,30,30,16,30,18,15,31,8608,22,78,30,30,29,30,28,30,30,30,           # 8600
 30,36,15,8622,30,16,30,8626,30,8628,30,15,29,88,30,30,30,30,15,52,       # 8620
 30,8640,30,16,30,30,30,8646,30,15,15,40,30,30,30,16,29,30,30,30,         # 8640
 30,15,29,8662,30,30,30,80,30,8668,30,30,31,15,15,24,30,8676,15,15,       # 8660
 15,8680,15,30,30,15,15,30,30,8688,30,15,15,8692,30,30,30,15,15,8698,     # 8680
 30,18,15,16,16,30,15,8706,30,15,15,30,30,8712,30,30,15,30,30,8718,       # 8700
 15,30,15,30,30,30,30,30,16,30,18,8730,15,30,22,30,30,8736,30,30,         # 8720
 28,8740,30,30,30,15,15,8746,30,30,30,30,30,8752,30,30,30,15,30,30,       # 8740
 30,8760,15,30,30,15,30,30,63,30,30,48,30,30,30,30,15,66,30,8778,         # 8760
 30,30,30,8782,30,30,30,30,15,30,30,58,30,30,30,30,22,30,30,30,           # 8780
 31,30,28,8802,30,30,30,8806,30,30,30,30,30,30,30,30,30,30,30,8818,       # 8800
 30,8820,30,30,30,30,30,30,30,80,30,8830,30,72,30,15,30,8836,30,8838,     # 8820
 30,15,30,36,30,30,30,30,30,8848,30,52,30,30,30,30,30,16,30,30,           # 8840
 30,8860,30,8862,31,15,15,8866,30,48,30,30,15,30,30,70,30,30,30,30,       # 8860
 30,82,30,15,30,28,30,8886,15,15,30,30,30,8892,30,16,63,15,30,30,         # 8880
 30,30,30,30,30,30,15,30,30,58,30,30,30,30,15,30,15,36,15,30,             # 8900
 15,30,30,8922,30,15,15,78,15,8928,30,30,15,8932,30,30,30,30,30,30,       # 8920
 30,8940,30,30,30,40,30,22,15,30,30,8950,30,30,30,15,15,52,15,30,         # 8940
 30,30,30,8962,30,30,30,30,30,8968,30,8970,30,18,30,30,16,46,18,15,       # 8960
 30,30,30,30,30,30,26,30,30,88,30,36,31,30,15,30,30,15,30,8998,           # 8980
 30,9000,30,15,15,30,30,9006,30,30,15,9010,30,9012,30,16,30,70,69,30,     # 9000
 30,66,15,30,30,30,30,60,15,9028,30,30,30,15,16,30,30,30,30,48,           # 9020
 30,9040,30,9042,30,15,28,82,30,9048,30,15,15,34,36,30,31,30,40,9058,     # 9040
 42,16,30,24,46,30,48,9066,30,18,52,46,30,42,15,15,58,30,60,30,           # 9060
 30,63,15,30,66,30,30,30,70,60,30,9090,15,30,15,30,30,30,30,30,           # 9080
 16,30,18,9102,15,30,22,30,30,9108,30,30,28,30,30,30,30,15,15,30,         # 9100
 30,30,30,30,30,72,30,9126,30,16,30,30,30,9132,15,30,30,9136,30,30,       # 9120
 30,30,30,40,30,15,15,30,15,30,30,9150,63,80,30,30,30,9156,30,30,         # 9140
 15,9160,30,16,30,30,30,88,15,52,30,30,30,9172,15,24,15,30,15,66,         # 9160
 30,9180,30,30,30,30,30,9186,30,30,30,30,30,28,15,15,30,30,30,9198,       # 9180
 30,30,30,9202,30,30,15,15,30,9208,30,60,15,15,30,30,30,30,15,30,         # 9200
 30,9220,30,22,15,30,15,9226,30,18,30,30,30,30,30,15,30,15,15,9238,       # 9220
 30,9240,30,30,15,30,30,16,31,30,30,30,30,18,15,15,30,9256,15,46,         # 9240
 15,26,30,58,30,16,15,15,15,15,15,72,71,15,30,68,30,9276,15,30,           # 9260
 63,9280,30,9282,15,30,15,36,16,15,18,30,15,9292,30,48,24,15,26,16,       # 9280
 28,70,30,31,15,17,30,40,36,30,30,9310,40,66,42,30,30,26,46,9318,         # 9300
 48,30,30,9322,52,24,30,15,15,30,58,17,60,30,30,63,68,9336,66,30,         # 9320
 30,9340,70,9342,72,30,30,15,15,9348,15,40,30,46,30,15,16,15,15,48,       # 9340
 30,15,15,15,30,15,30,16,15,26,15,9370,30,15,15,15,31,9376,15,82,         # 9360
 15,15,15,17,15,15,15,15,15,40,15,9390,15,15,15,15,15,9396,15,15,         # 9380
 15,15,15,9402,15,15,15,22,15,9408,15,15,15,9412,15,15,15,15,15,9418,     # 9400
 15,9420,15,26,15,15,15,15,15,15,15,9430,15,9432,15,15,15,9436,15,9438,   # 9420
 15,15,15,15,15,15,15,15,15,15,15,15,15,29,15,16,15,48,15,15,             # 9440
 15,9460,15,9462,15,15,15,9466,15,16,15,15,36,9472,15,24,15,18,15,9478,   # 9460
 15,18,15,15,15,23,15,52,15,16,15,9490,15,15,15,22,15,9496,15,26,         # 9480
 15,28,15,30,31,18,15,15,15,36,15,9510,15,17,15,15,15,30,30,15,           # 9500
 15,9520,15,88,15,15,15,30,15,30,15,26,15,9532,16,30,63,15,15,9538,       # 9520
 22,15,24,15,26,30,28,9546,30,30,30,9550,15,40,30,15,15,30,30,78,         # 9540
 30,15,15,72,30,30,30,30,31,30,30,17,15,15,15,30,30,60,30,15,             # 9560
 15,30,15,30,30,15,15,9586,30,42,30,15,15,52,15,30,30,15,30,30,           # 9580
 30,9600,15,15,15,15,30,30,15,15,15,30,15,9612,30,15,15,58,30,9618,       # 9600
 30,15,15,9622,30,30,30,15,15,9628,30,9630,31,15,15,30,15,30,30,15,       # 9620
 15,30,30,9642,30,30,15,30,30,9648,15,30,15,48,30,30,30,30,16,30,         # 9640
 18,9660,15,30,63,30,30,30,30,30,28,30,30,30,30,15,15,9676,30,9678,       # 9660
 30,30,30,30,30,30,30,15,30,9688,30,30,15,30,30,17,30,9696,30,30,         # 9680
 30,88,30,30,30,30,15,30,30,30,30,30,30,30,30,30,30,30,15,9718,           # 9700
 30,9720,30,30,30,30,22,70,30,30,30,36,28,9732,30,30,30,30,30,9738,       # 9720
 30,30,30,9742,30,30,30,30,30,9748,30,48,30,30,30,30,30,30,30,30,         # 9740
 30,42,30,30,30,16,30,9766,30,9768,30,16,30,30,30,30,30,30,30,30,         # 9760
 30,9780,30,30,30,30,30,9786,30,30,30,9790,30,30,30,16,15,96,30,40,       # 9780
 30,80,15,9802,30,15,30,30,30,30,30,9810,30,15,30,15,30,9816,15,15,       # 9800
 30,30,30,30,31,16,15,30,30,9828,30,30,30,9832,30,30,15,30,30,9838,       # 9820
 30,30,30,30,16,30,18,42,15,30,22,9850,30,58,30,30,28,9856,30,9858,       # 9840
 30,30,15,30,30,30,30,30,30,70,30,9870,30,30,30,78,30,30,17,30,           # 9860
 30,40,30,9882,30,30,30,9886,30,15,15,30,30,30,30,30,30,30,30,30,         # 9880
 30,9900,30,30,30,30,30,9906,30,30,30,30,30,30,30,30,30,46,30,15,         # 9900
 16,30,30,9922,30,24,30,30,30,9928,30,9930,30,30,30,30,30,39,15,15,       # 9920
 30,9940,30,60,30,30,30,30,30,9948,17,15,31,36,30,30,15,16,30,46,         # 9940
 30,30,15,40,30,30,30,9966,15,30,15,58,30,9972,30,30,30,30,30,30,         # 9960
 30,15,15,66,30,30,30,30,15,30,30,96,30,30,30,30,30,18,15,15              # 9980
)


def lower_bound(order: int) -> int:
    r"""
    Return the best known lower bound on the number of MOLS of
    the given ``order``.

    The source of this information is Table 3.87 in the Handbook of
    Combinatorial Designs, 2nd edition, by Colbourn and Dinitz. A few
    updates have subsequently been provided on Jeff Dinitz's website.

    Parameters
    ----------

    order : int
      The order (also known as the side) for which you'd like a lower
      bound on the number of MOLS instances. In the language of the
      Handbook, this is ``n``, and it should be between 0 and 9999.

    Returns
    -------

    int
      A lower bound on the number of MOLS.

    Raises
    ------

    IndexError
      If you ask for an order that isn't contained in the table.

    Examples
    --------

    There are no MOLS of order zero::

        sage: from sage.combinat.designs import MOLS_handbook_data
        sage: MOLS_handbook_data.lower_bound(0)
        0

    """
    return _LOWER_BOUNDS[order]
